#include <iostream>
using namespace std;

/**
 * @brief 
 * 从最左边的元素开始，并跟踪较小(或相等)元素的索引i。在遍历时，如果找到较小的元素，则将当前元素与arr[i]交换。否则，忽略当前元素。
 * 
 */

int partition(int arr[], int low, int high) {
    int pivot = arr[high];

    int i = low-1;
    
    for(int j = low; j <= high; j++) {
      
        if(arr[j] < pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }

    std::swap(arr[i+1], arr[high]);

    return i + 1;
}

int quick(int arr[], int low, int high) {
    
    if(low < high) {
        //  pi is the partition return index of pivot
       int pi = partition(arr, low, high);

       quick(arr, low, pi - 1);
       quick(arr, pi + 1, high);
    }

}

/*
output: 1 5 7 8 9 10
*/

int main() {
  int arr[]={10,7,8,9,1,5};
  int n=sizeof(arr)/sizeof(arr[0]);
  // Function call
  quick(arr, 0, n-1);
  //Print the sorted array
  cout<<"Sorted Array\n";
  for(int i=0;i<n;i++)
  {
    cout<<arr[i]<<" ";
  }
  return 0;
}
